\section{贪心算法}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{activity_max_num}
	\caption{可安排最大会议数}
	\label{fig:activity_max_num}
\end{figure}
现在有会议的开始和结束时间，11组会议，需要知道如何能安排最多的会议。例如活动$a_1$表示会议的开始和结束时间分别是1、4。会议安排的表格如下\figref{tab:activity_num}
\begin{table}[!htbp]
	\caption{会议安排时间}
	\centering
	\begin{tabular}{cccccccccccc}
		\toprule
		index            & 1 & 2 & 3 & 4 & 5 & 6 & 7  & 8  & 9  & 10 & 11 \\
		\midrule
		开始时间 $s_{index}$ & 1 & 3 & 0 & 5 & 3 & 5 & 6  & 8  & 8  & 3  & 12 \\
		结束时间 $f_{index}$ & 4 & 5 & 6 & 7 & 9 & 9 & 10 & 11 & 12 & 14 & 16 \\
		\bottomrule
	\end{tabular}
	\label{tab:activity_num}
\end{table}
会议的结束时间越早，越有可能给后面的会议安排（可安排的会议越多）。我们先对会议的结束时间从小到大排序，选中会议结束时间最早的会议，然后在剩下的会议集合中寻找刚好开始时间在其之后的会议，反复筛选直到最后一个会议。算法流程如下\figref{fig:activity_executable}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{activity_executable}
	\caption{会议室安排流程}
	\label{fig:activity_executable}
\end{figure}
更容易理解的办法是插入一个终点为0的开始结束时间对，但是从实现的角度往vector插入代价比较高，所以代码实现的时候使用了看起来不怎么优雅的为0判断然后再次操作。
\begin{listing}[!htbp]
	\caption{可安排最大会议数}
	\cppfile[firstline=2,lastline=20]{third_party/coding/cxx/algorithm/common/src/activitySelect.cc}
	\label{code:activitySelect}
\end{listing}

\subsection{\href{https://leetcode.cn/problems/jump-game/description/}{跳跃游戏}}
\begin{example}{跳跃游戏}{}
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
\end{example}
\begin{Mind}{能否跳跃}{}
从位置0开始尝试找到其作为起点能跳跃的最远距离，然后遍历到能到的最远距离继续如此。直到能到达的最大距离$\geq nums.size()$为止。
\end{Mind}
从起点开始，起点的数值决定了能跳多远。例如 nums[0] = 2 表示了在0这个位置最远能跳到位置2。那如果跳到位置1之后呢？可以跳到4（1+3），如果起点跳到2则下一跳只能跳到3（1+2）。所以需要从开头第一个元素到倒数第二个元素获取其能跳到的最远距离，如果距离超过了最后一个元素的下标则能跳到，否则不能。这里有一个错误思路：(判断i+num[i]是否超过最后一个元素位置的下标，错误在于你可能没法到达某一下标，比如：[0,1,2]，当你在0的时候你没法到达其它下标，直接为false，但是1能跳一下到目的地。)
\begin{listing}
	\caption{能否跳跃}
	\cppfile[firstline=3,lastline=10]{third_party/coding/cxx/algorithm/greedy/src/canJump.cc}
	\label{code:canJump}
\end{listing}
\coderef{code:canJump}中for循环的时候需要保证索引在能走到的最大范围以内。例如如果[3,2,1,0,4]这个case，从0、1、2三个位置最多都智能到达位索引为3的位置。所以索引i不可能为4，因此for循环中间有两个判断。
\subsection{\href{https://leetcode.cn/problems/jump-game-ii/description/}{跳跃游戏2}}
\begin{example}{跳跃游戏2}
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
\begin{itemize}
	\item 0 <= j <= nums[i]
	\item i + j < n
\end{itemize}
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

输入: nums = [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
\end{example}
\begin{Mind}{跳跃游戏2}{}
对于跳跃游戏中每个位置的跳跃值，我们可以得到在该跳跃点下能跳到的最大位置，比如nums[0]=2表示 在位置0可以跳到位置1和位置2。决定跳到哪里取决于哪个位置下的值谁更大，值越大说明选择这个位置之后下一步能跳的越远。最后跳跃的点如果超过了数组nums长度则结束。
\end{Mind}
算法流程如：
\begin{enumerate}
	\item start = 0 、end = 1，start 所在的值为2，表示在此位置能跳到1、2。因为nums[1] = 3，更新start = end，end = (0+2+1)（跳到start=0能跳到的最远距离的下一个位置）。
	\item start = 1 的时候所在值为3，能跳的最远距离为1+3=4，更新start = 4,end=更新到其下一个位置5，已经越界。
\end{enumerate}
最初的起点start=0，在此点如果能到达start那么end就是start+1。所以如果 nums = {0}，也可以获得正确的结果。需要注意的是我们更新的时候start=end、start=maxPos。只有在跳过了才将start更新到end而不是直接更新到maxPos+1。
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(1)。
\end{itemize}
\begin{listing}[!htbp]
	\caption{跳跃游戏2}
	\cppfile[firstline=3,lastline=17]{third_party/coding/cxx/algorithm/greedy/src/jump.cc}
	\label{code:jumpGame}
\end{listing}
\coderef{code:jumpGame}中跳跃最小值等价于最大跳跃距离能覆盖掉对应的位置下跳跃次数。按照贪心算法，每次都在对应的位置尽可能跳得更远，这个策略能获得全局最优解。因为最小跳跃次数这个最优解本质上和尽可能跳得更远是等价的。
\subsection{\href{https://leetcode.cn/problems/jump-game-iii/description/}{跳跃游戏III}}
这里有一个非负整数数组arr，你最开始位于该数组的起始下标start处。当你位于下标i处时，你可以跳到i + arr[i] 或者 i - arr[i]。请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。注意，不管是什么情况下，你都无法跳到数组之外。
\begin{Textcode}
	输入：arr = [4,2,3,0,3,1,2], start = 5
	输出：true
	解释：
	到达值为 0 的下标 3 有以下可能方案：
	下标 5 -> 下标 4 -> 下标 1 -> 下标 3
	下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
\end{Textcode}
跳跃线路如\figref{fig:dfs_jump}。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{dfs_jump}
	\caption{跳跃游戏示例}
	\label{fig:dfs_jump}
\end{figure}

\begin{Mind}{跳跃游戏III}{}
	DFS搜索，对于给定的位置每次可以在当前位置的基础上+nums[i]或者是-nums[i]。如果我们走到nums[i]=0则说明可以跳到对应的位置。通过 visited 维护已经到过的节点防止重复跳跃。
\end{Mind}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.5\textwidth]{canReach}
	\end{center}
	\caption{跳跃游戏III示意图}
	\label{fig:canReach}
\end{figure}
举个例子，当前位置 5，线路选择如\figref{fig:canReach}，代码实现\coderef{code:jumpGame3}。
\begin{itemize}
	\item 可以选择跳到4。
	      \begin{itemize}
		      \item 4可以选择跳到1和7。
		            \begin{itemize}
			            \item 1跳到-1，越界停止。
			            \item 跳到3值为0，返回true。
		            \end{itemize}
		      \item 跳到7，越界停止。
	      \end{itemize}
	\item 选择跳到6。
	      \begin{itemize}
		      \item 跳到4，发现4之前已经访问过，停止。
		      \item 跳到8，越界停止。
	      \end{itemize}
\end{itemize}

\begin{listing}[!htbp]
	\caption{跳跃游戏3}
	\cppfile[firstline=18,lastline=34]{third_party/coding/cxx/algorithm/greedy/src/jump.cc}
	\label{code:jumpGame3}
\end{listing}
\subsection{\href{https://leetcode.cn/problems/jump-game-vi/description/}{跳跃游戏VI}}
\begin{example}

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到[i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。请你返回你能得到的 最大得分。
\begin{Textcode}
示例 1：

输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。

示例 2：

输入：nums = [10,-5,-2,4,0,3], k = 3
输出：17
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。

示例 3：

输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出：0
\end{Textcode}
\end{example}
动态规划实现，dp[i]表示从0跳到i（包含i）获得的最大值，它可以从i之前k个状态转移到当前，取决于哪个状态能获得更大的值。$dp[i]=dp[i-k]\quad j=1\ldots k$，值得注意的是直接这样做超时，因为遍历每个元素的时候还需要遍历前k个元素，时间复杂度为O(kn)。可以通过维护一个k个元素的单调队列，这样时间复杂度能降到O(n)。
\begin{listing}[H]
	\caption{跳跃游戏4}
	\cppfile[firstline=3,lastline=21]{third_party/coding/cxx/algorithm/dp/src/maxResult.cc}
	\label{code:jumpGame4}
\end{listing}
\coderef{code:jumpGame4}的实现中使用双端队列，队列头部元素为索引i之前符合要求（最多k个元素）最大的结果。取数据的时候从队列头的元素就是最大元素，于是加数据的时候需要特殊操作：如果当前result大于队列尾部的元素的时候pop尾部的元素直到发现队尾元素小于result时将结果入队列。
\begin{enumerate}
	\item i=0的时候result=1，queue = [(1,0)]。
	\item i=1的时候result=1-1=0，queue=[(1,0),(0,1)]。
	\item i=2的时候result=1-2=-1，queue=[(0,1),(-1,2)]。
	\item i=3的时候result=0+4=4，queue=[(4,3),(-1,2)]。
	\item i=4的时候result=4-7=-3，queue=[(4,3),(-3,4)]。(这里出队列(-1,2)然后入当前的最小值)
	\item i=5的时候result=4+3=7，queue=[(4,3),(7,5)]
\end{enumerate}
\coderef{code:jumpGame4}第一个while循环将比较大的元素从左边移走，第二个while将右边的元素移走。
\subsection{加油站}
\begin{example}[加油站]
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
\begin{Textcode}
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
\end{Textcode}
\end{example}
\begin{Mind}{加油站}{}
	简单朴素的做法是从加油站每个位置作为起点尝试走到相同的位置。但是这样会重复多次，比如：如果从位置i走到了位置j发现走不通，这意味着[i,j]中间的任意一个点都不可能走通。此时应该直接从j+1开始走。
\end{Mind}
\begin{longlisting}
	\caption{加油站}
	\cppfile[firstline=4,lastline=18]{third_party/coding/cxx/algorithm/greedy/src/canCompleteCircuit.cc}
	\label{code:canCompleteCircuit}
\end{longlisting}
\coderef{code:canCompleteCircuit}中，如果消耗的总汽油>加油总量则一定无法到达。遍历加油站的时候记录下这个消耗差异。
\subsection{IPO}
\begin{example}[IPO]
假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。答案保证在 32 位有符号整数范围内。

示例 1：
\begin{Textcode}
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4

\end{Textcode}
解释：由于你的初始资本为 0，你仅可以从 0 号项目开始。在完成后，你将获得 1 的利润，你的总资本将变为 1。此时你可以选择开始 1 号或 2 号项目。由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
示例 2：
\begin{Textcode}
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6
\end{Textcode}
\end{example}
\begin{Mind}{IPO}{}
找到对应可投资的capital(w>=capital[i])项目，然后找到可投资项目中收益最大的结果加入w。接着对更新之后的w做相同的操作，直到满足k次投资为止。
\end{Mind}
我们需要方便的找到可投资项目中收益最大的项目，这里使用最大堆将索引对应的最大收益加入最大堆，这样就可以方便的更新w。为了方便的判断满足条件的投资项目（w>capital[i]），我们对capital排序这样发现w<capital[i]就不用继续对比了，因为capital的索引和profits的索引对应，所以排序也得和profits一起。
\begin{longlisting}
	\caption{IPO}
	\cppfile[firstline=4,lastline=31]{third_party/coding/cxx/algorithm/greedy/src/findMaximizedCapital.cc}
	\label{code:findMaximizedCapital}
\end{longlisting}
\coderef{code:findMaximizedCapital} 最多累计k次profit。所以外层循环k次，如果available为空意味着没有找到能投资的项目，此时可以提前结束。

